package mashibing.class11;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化反序列树（中序遍历树无法序列话，存在歧义）
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-05-17
 */
public class Class11_2_SerializeAndReconstructTree {
    /*
     * 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化，
     * 以下代码全部实现了。
     * 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
     * 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
     * 比如如下两棵树
     *         __2
     *        /
     *       1
     *       和
     *       1__
     *          \
     *           2
     * 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
     *
     * */
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    // 先序序列化
    public static Queue<String> preSerial(Node root) {
        if (root == null) {
            return null;
        }
        Queue<String> queue = new LinkedList<>();
        preSerialProcess(root, queue);
        return queue;
    }

    public static void preSerialProcess(Node head, Queue<String> queue) {
        if (head == null) {
            queue.add(null);
            return;
        }
        queue.add(String.valueOf(head.value));
        preSerialProcess(head.left, queue);
        preSerialProcess(head.right, queue);
    }

    private static Node buildByPreQueue(Queue<String> pre) {
        if (pre == null || pre.size() == 0) {
            return null;
        }
        String pollStr = pre.poll();
        if (pollStr == null) {
            return null;
        }
        Node head = new Node(Integer.parseInt(pollStr));
        head.left = buildByPreQueue(pre);
        head.right = buildByPreQueue(pre);
        return head;
    }

    // 层级序列化
    private static Queue<String> levelSerial(Node head) {
        Queue<String> result = new LinkedList<>();
        if (head == null) {
            result.add(null);
            return result;
        }
        result.add(String.valueOf(head.value));
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            head = queue.poll();
            if (head.left != null) {
                queue.add(head.left);
                result.add(String.valueOf(head.left.value));
            } else {
                result.add(null);
            }
            if (head.right != null) {
                queue.add(head.right);
                result.add(String.valueOf(head.right.value));
            } else {
                result.add(null);
            }
        }
        return result;
    }

    private static Node buildByLevelQueue(Queue<String> queue) {
        if (queue == null || queue.size() == 0) {
            return null;
        }
        String pollStr = queue.poll();
        if (pollStr == null) {
            return null;
        }
        Queue<Node> nodeQueue = new LinkedList<>();
        Node head = new Node(Integer.parseInt(pollStr));
        nodeQueue.add(head);
        while (!nodeQueue.isEmpty()) {
            Node poll = nodeQueue.poll();
            String leftStr = queue.poll();
            if (leftStr != null) {
                Node left = new Node(Integer.parseInt(leftStr));
                poll.left = left;
                nodeQueue.add(left);
            }
            String rightStr = queue.poll();
            if (rightStr != null) {
                Node right = new Node(Integer.parseInt(rightStr));
                poll.right = right;
                nodeQueue.add(right);
            }
        }
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 5;
        int maxValue = 100;
        int testTimes = 1000000;
        System.out.println("test begin");
        for (int i = 0; i < testTimes; i++) {
            Node head = generateRandomBST(maxLevel, maxValue);
            Queue<String> pre = preSerial(head);
//            Queue<String> pos = posSerial(head);
            Queue<String> level = levelSerial(head);
            Node preBuild = buildByPreQueue(pre);
//            Node posBuild = buildByPosQueue(pos);
            Node levelBuild = buildByLevelQueue(level);
//            if (!isSameValueStructure(preBuild, posBuild) || !isSameValueStructure(posBuild, levelBuild)) {
//                System.out.println("Oops!");
//            }
            if (!isSameValueStructure(preBuild, levelBuild)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("test finish!");
    }

    private static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    private static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static Node generateNode(String val) {
        if (val == null) {
            return null;
        }
        return new Node(Integer.parseInt(val));
    }

    private static boolean isSameValueStructure(Node node1, Node node2) {
        if (node1 == null && node2 == null) {
            return true;
        }
        if (node1 == null || node2 == null) {
            return false;
        }
        if (node1.value != node2.value) {
            return false;
        }
        return isSameValueStructure(node1.left, node2.left) && isSameValueStructure(node1.right, node2.right);
    }

}
